GATE CSE 2023
Q11.
Which one or more of the following CPU scheduling algorithms can potentially cause starvation?Q12.
Suppose two hosts are connected by a point-to-point link and they are configured to use Stop-and-Wait protocol for reliable data transfer. Identify in which one of the following scenarios, the utilization of the link is the lowest.Q13.
Let f:A\rightarrow B be an onto (or surjective) function, where A and B are nonempty sets. Define an equivalence relation \sim on the set A as a_1\sim a_2 \text{ if } f(a_1)=f(a_2), where a_1, a_2 \in A . Let \varepsilon =\{[x]:x \in A\} be the set of all the equivalence classes under \sim . Define a new mapping F: \varepsilon \rightarrow B as F([x]) = f(x), for all the equivalence classes [x] in \varepsilonWhich of the following statements is/are TRUE?Q14.
Let G be a simple, finite, undirected graph with vertex set \{v_1,...,v_n\}. Let \Delta (G) denote the maximum degree of G and let N=\{1,2,...\} denote the set of all possible colors. Color the vertices of G using the following greedy strategy: for i = 1,...,n color(v_i)\leftarrow min\{ j \in N: \text{ no neighbour of } v_i \text{ is colored } j\} Which of the following statements is/are TRUE?Q15.
Let U = \{1, 2, 3\}. Let 2^U denote the powerset of U. Consider an undirected graph G whose vertex set is 2^U. For any A,B \in 2^U, (A,B) is an edge in G if and only if (i) A \neq B, and (ii) either A \subseteq B or B \subseteq A. For any vertex A in G, the set of all possible orderings in which the vertices of G can be visited in a Breadth First Search (BFS) starting from A is denoted by B(A). If \phi denotes the empty set, then the cardinality of B(\phi ) is ____.Q16.
Consider the following program: int main() { f1(); f2(2); f3(); return(0); } int f1() { return(1); } int f2(int X) { f3(); if (X==1) return f1(); else return (X*f2(X-1)); } int f3() { return(5); } Which one of the following options represents the activation tree corresponding to the main function?Q17.
The integer value printed by the ANSI-C program given below is ______.#include < stdio.h > int funcp(){ static int x = 1; x++; return x; } int main(){ int x,y; x = funcp(); y = funcp()+x; printf("%d\n", (x+y)); return 0; }Q18.
An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let k be the number of keys, m be the number of slots in the hash table, and k \gt m. Which one of the following is the best hashing strategy to counteract the adversary?Q19.
Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation Extract-Max(A) extracts and deletes the maximum element from A. The operation Insert(A,key) inserts a new element key in A. The properties of a max-heap are preserved at the end of each of these operations. When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?Q20.
Which one of the following sequences when stored in an array at locations A[1], . . . , A[10] forms a max-heap?